//
// Created by Senhai Xu on 2024/7/4.
//
#include <iostream>
#include<vector>
#include<queue>
#include <algorithm>
#include <map>
using namespace std;
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
//     构造函数（非默认）
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

//方法1 层序遍历+为遍历到的每个节点添加父节点属性
//找到节点1的路径，然后从另一个节点2往上找，直到找到相同的节点
//需要用到的数据结构 一个map 记录节点的父节点； 队列 用于层序遍历
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        if (root == nullptr) return -1;
        map<int, int> parentMap;
        parentMap[root->val] = root->val;
        queue<TreeNode*> q;
        q.push(root);
//遍历找到两个元素
        while (parentMap.find(o1)->first && parentMap.find(o2)->first && !q.empty()) {
            TreeNode* node = q.front();
            q.pop();
//在队列中弹出一个节点，判断其左右子节点是否为空，不为空则将子节点加入队列，并将子节点的父节点加入map中
            if (node->left) {
                parentMap[node->left->val] = node->val;
                q.push(node->left);
            }
            if (node->right) {
                parentMap[node->right->val] = node->val;
                q.push(node->right);
            }
        }
//        找到o1的路径
        vector<int> path1;
        while (o1 != root->val) {
            path1.push_back(o1);
            o1 = parentMap[o1];
        }
        path1.push_back(root->val);

        while (find(path1.begin(), path1.end(), o2) == path1.end()) {
            o2 = parentMap[o2];
        }
        return o2;
    }


};

//方法二 二叉树的递归遍历
class Solution2 {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        if (root == nullptr) return -1;//超过叶节点 返回空
        if (root->val == o1 || root->val == o2) return root->val;//找到o1 o2 返回o1 o2
        int left = lowestCommonAncestor(root->left, o1, o2);//递归遍历左子树
        int right = lowestCommonAncestor(root->right, o1, o2);//递归遍历右子树
        if (left != -1 && right != -1) return root->val;//如果左右子树都有值，则说明o1o2分别在左右子树，返回root
        if (left == -1) return right;//如果左子树没有值，则说明o1在右子树，返回右子树
        if (right == -1) return left;//如果右子树没有值，则说明o2在左子树，返回左子树
        else return  -1;
        }
};


//方法三 DFS+递归 遍历两次 找到遍历路径
class Solution3 {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
     bool find = false;
    void dfs(vector<int>& load, TreeNode* root, int o) {
        if(find || root == nullptr) return; //已经找到或者到达空节点
        load.push_back(root->val); //加入数组
        if(root->val == o) {
            find = true;
            return;
        }
        dfs(load, root->left, o);
        dfs(load, root->right, o);
        if(find) { //防止将节点去除
            return;
        }
        load.pop_back(); //不在这条路径，去除节点
    }

    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        vector<int> load1, load2;
        dfs(load1, root, o1); //找到 root到o1路径
        find = false; //重置标记
        dfs(load2, root, o2); //找到 root到o2路径
        int len = min(load1.size(), load2.size());
        //寻找最后一个相等节点
        for(int i = 1; i < len; ++i) {
            if(load1[i] != load2[i]) {
                return load1[i - 1];
            }
        }
        return load1[len - 1];
    }
};
int main() {
    // Test case 1
    TreeNode *root1 = new TreeNode(3);
    root1->left = new TreeNode(5);
    root1->right = new TreeNode(1);
    root1->left->left = new TreeNode(6);
    root1->left->right = new TreeNode(2);
    root1->right->left = new TreeNode(0);
    root1->right->right = new TreeNode(8);
    root1->left->right->left = new TreeNode(7);
    root1->left->right->right = new TreeNode(4);

    Solution3 solution;
    cout << "Test case 1: " << solution.lowestCommonAncestor(root1, 6, 5) << endl; // Output: 3
}